import com.sun.tools.javac.Main;

import javax.xml.transform.Source;

/**
 * @Description: 重复的子字符串
 * 给定一个非空的字符串 s ，
 * 检查是否可以通过由它的一个子串重复多次构成。
 * @Date:Create in 21:00  2022/7/11
 */
public class repeatedSubstringPattern0459 {
    public static void main(String[] args) {
        String s = "aba";
        int[] next =new int[s.length()];
        getNext(next,s);
        for(int i:next) System.out.println(i);
        System.out.println(repeatedSubstringPattern(s));
    }

    public static boolean repeatedSubstringPattern(String s) {
        if(s.equals("")) return false;
        int size = s.length();
        int[] next =new int[s.length()];
        getNext(next,s);

        if(next[size-1]>0 && size%(size-next[size-1])==0) return true;

        return false;
    }

    //获得前缀表
    public static void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) j++;
            next[i] = j;
        }
    }
}
